//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
// 
//
// 示例 2： 
//
// 
//输入：height = [4,2,0,3,2,5]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 1 <= n <= 2 * 10⁴ 
// 0 <= height[i] <= 10⁵ 
// 
//
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 5786 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	// public int trap(int[] height) {
	// 	// 计算公式：每个元素 min(前面的最大值，后面的最大值） - 当前元素
	// 	int n = height.length;
	// 	// 初始化，两个最大数组
	// 	int[] leftMax = new int[n];
	// 	leftMax[0] = height[0];
	// 	int[] rightMax = new int[n];
	// 	rightMax[n - 1] = height[n - 1];
	// 	// 计算最大值
	// 	for (int i = 1, j = n - 2; i < n; i++,j--){
	// 		// left最大的和当前进行比较保存最大值
	// 		leftMax[i] = Math.max(leftMax[i - 1], height[i]);
	// 		// 	right最大的当前进行比较，保存最大值
	// 		rightMax[j] = Math.max(rightMax[j + 1], height[j]);
	// 	}
	// 	// 重新遍历计算结果
	// 	int ans = 0;
	// 	for (int i = 1; i < n - 1; i++) {
	// 		// 计算公式：每个元素 min(前面的最大值，后面的最大值） - 当前元素
	// 		ans += Math.min(leftMax[i], rightMax[i]) - height[i];
	// 	}
	// 	return ans;
	// }
	
	// 相向双指针
	// 时间复杂度：o(n)
	// 空间复杂度：o(1)
	public int trap(int[] height) {
		int ans = 0;//总和
		int n = height.length;
		// 	记录left和right的最大值
		int leftMax = 0;
		int rightMax = 0;
		// 	初始化相向双指针
		// 	循环从 1 ~ n - 2.第一个和最后一个不用循环判断
		int left = 0;
		int right = n - 1;
		
		while (left < right) {
			// 	min = min（leftMax，rightMax）
			// 	那个小那个移动 left++，right--
			// 计算公式 ：移动
			while (left < right && height[left] <= height[right]) {
				// 左边小或者相等，那么左边移动。
				// 获取左边最大值
				leftMax = Math.max(leftMax, height[left]);
				// 进行计算：左边最大值 - 当前。
				ans += leftMax - height[left];
				left++;
			}
			// 右边同理
			while (left < right && height[right] <= height[left]) {
				rightMax = Math.max(rightMax, height[right]);
				ans += rightMax - height[right];
				right--;
			}
		}
		return ans;
		
		
	}
}
//leetcode submit region end(Prohibit modification and deletion)
